package com.leetcode.二叉树;


/**
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * @author LZF
 *
 */
public class L110平衡二叉树 {
	public static void main(String[] args) {
		
	}
	/**
	 * 这个做法，当root是满足平衡二叉树的条件时，我们已经计算了root左右子树的高度，但是此时我们还要继续判断root的左右子树的高度是否满足平衡二叉树的条件，
	 * 就要再次计算'root子树'的'左右子树'的高度，这样存在重复计算。修改：见isBalancedNew()。
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
		if (root == null) return true;
		// 计算左右子树的深度
		int depthL = cntTreeDepth(root.left);
		int depthR = cntTreeDepth(root.right);
		// 判断root是否满足平衡二叉树的条件
		if (Math.abs(depthL - depthR) > 1) return false;
		// root满足，再判断root的左右子树是否满足
		return isBalanced(root.left) && isBalanced(root.right);
    }
	
	/**
	 * 计算一个树的深度
	 * @param node
	 * @return
	 */
	public int cntTreeDepth(TreeNode node) {
		if (node == null) return 0;
		int cntL = cntTreeDepth(node.left);
		int cntR = cntTreeDepth(node.right);
		return 1 + Math.max(cntL, cntR);
	}
	
	/**
	 * 改进：让节点的val存放该节点的高度，用-1作为标记表示该节点不满足平衡二叉树的条件
	 * 这个方法还是利用了深搜，深搜可以最先遍历到最底层，所以这里会最底层开始计算每个节点的高度
	 * 因此只需要判断root的高度是否为-1，就可以判断整个树是否为平衡二叉树
	 * @param 
	 * @return
	 */
	public int cntTreeDepthNew(TreeNode node) {
		if (node == null) return 0;
		int depthL = cntTreeDepthNew(node.left);
		int depthR = cntTreeDepthNew(node.right);
		// 左右子树的高度存在一个为-1，说明左右子树不是平衡二叉树，那当前整个树也不是平衡二叉树
		if (depthL == -1 || depthR == -1) {
			node.val = -1;
			return -1;
		}
		int depth = 1 + Math.max(depthL, depthR);
		// 如果左右子树的高度不满足平衡二叉树的条件，那将当前节点的高度设为-1，作为标记
		if (Math.abs(depthL - depthR) > 1) {
			depth = -1;
		}
		node.val = depth;
		return depth;
	}
	
	public boolean isBalancedNew(TreeNode root) {
		return cntTreeDepthNew(root) != -1;
	}

	//树的定义
		public class TreeNode {
			int val;
			TreeNode left;
			TreeNode right;

			TreeNode(int val) {
				this.val = val;
			}

			TreeNode(int val, TreeNode left, TreeNode right) {
				this.val = val;
				this.right = right;
			}
		}
}
